package leecode;

import javax.swing.tree.TreeNode;
import java.util.HashMap;
import java.util.Map;

/**
 * 功能描述：
 *
 * @Author: lwg
 * @Date: 2021/4/5 17:10
 */
public class demo07 {
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //获取树节点的总长度
        int n = preorder.length;
        //利用哈希映射来快速定位节点的位置
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            //键代表节点的值,值代表节点的下标位置
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            //此时表示遍历的位置超出
            return null;
        }
        //前序遍历的第一个数就是根节点,此属性为根节点在前序遍历中的位置
        int preorder_root = preorder_left;
        //查询得到中序遍历中根节点的位置
        int inorder_root = indexMap.get(preorder[preorder_root]);
        //得到中序遍历中的左节点的个数
        int left_size = inorder_root - inorder_left;
        //构建根节点
        TreeNode root = new TreeNode(preorder[preorder_root]);
        //递归构建左子树,并连接到根节点
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + left_size,
                inorder_left, inorder_root - 1);
        //递归构建右子树
        root.right = myBuildTree(preorder, inorder, preorder_root + left_size + 1,
                preorder_right, inorder_root + 1, inorder_right);
        return root;

    }

  /*  public TreeNode buildTree(int[] preorder, int[] inorder) {
        //1.获取树的长度
        int n = preorder.length;
        //2.利用hashMap来存取中序遍历节点的值，方便后续查找到根节点在中序遍历中的位置，不用再依次遍历
        HashMap<Integer, Integer> indexHash = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexHash.put(inorder[i], i);
        }
        //3.递归构建二叉树
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        //1.限制遍历的长度
        if (preorder_left > preorder_right) {
            //超出界限
            return null;
        }
        //2.获取前序遍历中根节点的位置
        int preorder_root = preorder_left;
        //3.利用hashMap获取根节点在中序遍历中的位置
        int inorder_root = indexMap.get(preorder[preorder_root]);
        //4.获得中序遍历中左子节点的个数
        int left_size = inorder_root - inorder_left;
        //5.创建根节点
        TreeNode root = new TreeNode(preorder[preorder_root]);
        //6.递归创建左子节点
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + left_size,
                inorder_left, inorder_root - 1);
        //7.递归创建右子节点
        root.right = myBuildTree(preorder, inorder, preorder_root + left_size + 1,
                preorder_right, inorder_root + 1, inorder_right);
        return root;
    }*/

    class TreeNode {
        //数据域
        public int data;
        //左指针域
        public TreeNode left;
        //右指针域
        public TreeNode right;

        public TreeNode(int data, TreeNode left, TreeNode right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "leecode.demo07.TreeNode{" +
                    "data=" + data +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public static void main(String[] args) {
        int preorder[] = {3, 9, 20, 15, 7};
        int inorder[] = {9, 3, 15, 20, 7};
        demo07 demo07 = new demo07();
        TreeNode treeNode = demo07.buildTree(preorder, inorder);
        System.out.println(treeNode);
    }
}
